CRDT (conflict-free replicated data type)
CvRDT (convergent replicated data type。state-based CRDT)
構成要素
data 型
local の狀態 (state)
狀態を他の node へ傳播する
差分だけを傳播する algorithm もある
狀態に對する作用 (action)
函數
初期狀態 (initial state) を生成する函數
複數の狀態を倂合 (merge) する函數
狀態に action を適用して更新する函數
counter
狀態 {node_id => count}
初期狀態 {node1: 0, node2: 0, ..., node_n: 0}
操作
increment state[node_self] += 1
倂合
※擬似 code なので他の言語に近い for 文を使ふよ
code:ruby
for node_id in state.keys do
end
node の參加は容易い
positive-negative counter
狀態 {positive: {node_id => 0}, negative: {node_id => 0}}
操作
increment state[:positive][node_self] += 1
decrement state[:negative][node_self] += 1
狀態の取得
state[:positive][node_self] - state[:negative][node_self]
倂合
code:ruby
for node_id in state.keys do
end
集合
初期狀態$ \varnothing
操作
add$ S\cup\{e\}
merge$ S\cup T
初期狀態 {added: Set[], removed: Set[]}
操作
add state[:added].add(new_element)
remove state[:removed].add(new_element)
一度消した要素は再追加できない
狀態の取得 state[:added] - state[:removed]
倂合 {added: state[:added] | received_state[:added], removed: state[:removed] | received_state[:removed]}
LWW-element-set (last-write-wins-element-set)
OR-set (observed-remove set)
消した要素を忘れる最適化が可能
複製データの結果整合性モデルは、同時更新を可能にし、遲延を低減するとともに、耐障礙性を向上させるが、强い整合性は犠牲にする。このため、複數のクラウドコンピューティングプラットフォームでは、結果的に整合性が保證されるデータ型が實裝されてゐる。集合は廣く普及し有用な抽象槪念であり、これまでに數多くの複製集合の設計が提案されてきた。本硏究では、竝行型の期待される竝行性意味論を體系的に記述するための推論抽象槪念として、置換等價性を提案する。この枠組みに基づき、既存の競合フリー複製データ型の一つである「觀測削除集合」を紹介する。さらにメタデータのサイズ削減を目的として、墓石データ (tombstones) を囘避する新たな最適化手法を提案する。この手法はマップ、グラフ、シーケンスなどの他のデータ型にも適用可能である。
狀態
code:typescript
{
elements:, {element: any, count: Date, replica: NodeId}[],
counter: {NodeId: Integer},
}
初期狀態
code:ruby
{
elements: Set[],
counter: {node1: 0, node2: 0, ..., node_n: 0},
}
操作
add
code:ruby
state:elements.add({element: new_element, count: count, replica: node_self}) remove state[:elements].delete_if {|e| e[:element] = element }
倂合
code:ruby
u = m | mm | mmm
# 各 element 每に count が最大のものを選ぶ
o = u.to_a.to_set.keep_if {|e| 〜 }
e = u - o
state = {elements: e, counter: v}
sequence
Treedoc
RGA
協調作業を必要とする分散アプリケーションにおいては、應答性が高く透明性のある雙方向性が强く求められる。このやうな雙方向性は樂觀的レプリケーションによって實現可能ではあるものの、レプリカ閒の一貫性維持は困難な課題である。本論文では、協調アプリケーションの效率的な實裝を支援するため、配列、ハッシュテーブル、擴張可能な配列 (またはリンクリスト) といった代表的な抽象データ型 (ADT) を、複製可能な抽象データ型 (RADT) へと擴張する。RADT では、共有 ADT を複製し、樂觀的操作によって變更を加へる。操作の可換性と前順性といふ 2 つの原則により、RADT は異なる實行順序においても一貫性を維持することが可能となる。特に、複製可能な擴張配列 (RGA) は挿入/削除/更新操作をサポートしてゐる。從來の樂觀的挿入・削除手法と比較して、RGA は性能、スケーラビリティ、および信賴性の面で顯著な改善を示してゐる。
Woot
P2P (peer to peer)ネットワークはコンテンツ配信において極めて效率的なシステムである。本硏究では、この特性を活用し、單なるコンテンツ配信にとどまらず、共同編輯機能を實現することを目指す。既存の共同編輯システムは中央集權型か、あるいはサイト數に依存する設計となってゐる。このやうなシステムは、P2P (peer to peer)ネットワーク上に展開した場合に擴張性に限界が生じる。本論文では、新たな共同編輯システム構築モデルを提案する。このモデルは完全に分散型であり、サイト數に依存しない設計となってゐる。 Logoot-Undo
LogootSplit
LSEQ
分散型共同編輯システムは、時閒・空閒・組織の枠を超えてユーザーが共同作業を行ふことを可能にする。Google Docs、Etherpad、Git といった代表的な分散型共同編輯ツールは、長年にわたってその利用が擴大してきた。近年、複數のサイトに複製された分散データ構造群を基盤とする新たなタイプの分散型エディタが登場した。これは「競合フリー複製データ型」(CRDT (conflict-free replicated data type) : Conflict-free Replicated Data Type) と呼ばれる槪念に基づくものである。本論文では、基本要素 (行・單語・文字など) からなる分散シーケンスを表現する CRDT (conflict-free replicated data type) について考察する。このシーケンスに対して可能な操作は、要素の挿入と削除である。既存技術との比較において、本手法はより分散型のアーキテクチャを採用してをり、參加者數の增加に對してより優れたスケーラビリティを發揮する。ただし、空閒計算量は文書への總插入囘數と插入位置の總數に對して線形となる。このため、このやうなエディタの綜合的な性能はユーザーの編輯行動に大きく依存することになる。本論文では、シーケンス CRDT (conflict-free replicated data type) 向けの適應型割り當て戰略である LSEQ を提案し、そのモデル化を行う。LSEQ は平均的なケースにおいて、編輯行動の如何にかかわらずサブ線形の空閒計算量を達成する。一聯の實驗により LSEQ の有效性を檢證した結果、既存の手法を凌駕する性能を示すことが確認された。 LSEQSplit
リアルタイム共同編輯ツールは、空閒的・時閒的・組織的な制約を超えて作業を分散させる一般的なソリューションとして廣く利用されてゐる。しかしながら、Google Docs などの主流のエディタは中央サーバーに依存してをり、プライバシー保護やスケーラビリティの面で課題を抱へてゐる。CRATE は WebRTC 技術を活用することで、ウェブブラウザ上で直接動作する分散型リアルタイム共同編輯ツールである。最先端のソリューションと比較して、CRATE は共同編輯をサポートするためにブラウザのみを必要とする點で初のリアルタイムエディタであり、小規模グループから大規模グループまでのユーザー環境を透明性を持ってシームレスに處理できる。このため、CRATE は大規模オンライン講義やテレビ番組、大規模カンファレンスなど、ユーザーがノートを共有する必要がある場面でも活用できる。CRATE の特性は以下の 2 つの科學的成果に基づいてゐる : (i) 空閒計算量に対してサブ線形の上限を持つ複製シーケンス構造――これによりエディタはコストのかかる分散型ガベージコレクタの實行を囘避できる、(ii) 適應型ピアサンプリングプロトコル――これによりエディタはルーティングテーブルを過剩に肥大化させることを防ぎ、結果として小規模ネットワークが大規模ネットワークのコストを負擔させられる事態を囘避できる。本論文では CRATE の詳細な仕樣、その特性、および實際の使用方法について體系的に說明する。 CmRDT (commutative replicated data type。operation-based CRDT)
實裝
Yjs